/* 幂乘 ，计算a^b % c
 * 主要原理：
 * 1. 使用反复平方方，快速计算幂乘，即：
 * if b为偶数，a^b = (a^2)^(b/2)
 * if b为奇数，a^b = (a^2)^(b/2) * a
 * 2. (a * b) % c = (a % c) * (b % c) % c
 */

#include<cstdint>
#include<iostream>
using namespace std;

int64_t mod_pow(int64_t a, int64_t b, int64_t c)
{
	int64_t res = 1;
	int64_t x = a;
	while (b > 0)
	{
		if (b % 2 != 0)
		{
			res = res * x % c;
		}

		x = x * x;
		
		b /= 2;
	}

	return res;
}

int main(void)
{
	cout<< mod_pow(8, 5, 17) <<endl;

	return 0;
}
